/**
 * 二叉搜索树
 */

function createArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(Math.floor(Math.random() * n));
  }
  return arr;
}

const arr = createArray(10000);
console.log("▶『arr』", arr);

function Node(val) {
  this.value = val;
  this.left = null;
  this.right = null;
}

/**
 * 向二叉搜索树中添加节点
 * @param {Object} node - 当前节点
 * @param {number} val - 新节点的值
 */
function addNode(node, val) {
  if (node == null) return;
  if (node.value == val) return;
  if (node.value < val) {
    if (node.right == null) node.right = new Node(val);
    else addNode(node.right, val);
  } else {
    if (node.left == null) node.left = new Node(val);
    else addNode(node.left, val);
  }
}

/**
 * 构建二叉搜索树
 * @param {Array} arr - 用于构建树的数组
 * @returns {Object|null} - 返回构建的二叉搜索树的根节点，如果数组为空则返回null
 */
function buildSearchTree(arr) {
  if (arr == null || arr.length === 0) return null;
  const root = new Node(arr[0]);
  for (let i = 1; i < arr.length; i++) {
    addNode(root, arr[i]);
  }
  return root;
}

/**
 * 通过二叉树搜索值
 * @param {Object} tree - 二叉搜索树
 * @param {number} val - 需要搜索的值
 * @returns {boolean} - 如果找到值返回true，否则返回false
 */
function searchByTree(tree, val) {
  if (tree == null) return;
  if (tree.value === val) return true;
  return searchByTree(val < tree.value ? tree.left : tree.right, val);
}


const tree = buildSearchTree(arr);
const bool = searchByTree(tree, 1000);
console.log("▶『bool』", bool);
